package com.xiang.xian.array;

/**
 * @Author Xiang.Xian
 * @Description
 * @Date 2025/01/09/21:33
 * @Version 1.0
 * <p>
 * 无序数组找到第k大的数：写出两种做法，如quick select和heap
 */

public class QuickSelect {
    public static void main(String[] args) {
        int[] arr = {2, 8, 5, 6, 9, 11, 1, 3, 7};

        int k = 3;
        // 传3 代表 第三小， 第K大 得倒过来
        int realK = arr.length - k;
        int i = quickSelect(arr, 0, arr.length - 1, realK);
        System.out.println(i);
    }


    //从小到大 第K小
    public static int quickSelect(int[] arr, int low, int high, int k) {

        if (low == high) {
            return arr[low];
        }
        int index = partition(arr, low, high);
        if (index == k) {
            return arr[index];
        } else {
            if (k < index) {
                return quickSelect(arr, low, index - 1, k);
            } else {
                return quickSelect(arr, index + 1, high, k);

            }
        }

    }

    //找到基准元素所 应该排在的 位置
    public static int partition(int[] arr, int low, int high) {

        int pivotIndex = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivotIndex) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }

        int temp = arr[i];
        arr[i] = pivotIndex;
        arr[high] = temp;
        return i;
    }

}
